package cn.wgx.study.algorithm;

import java.util.Arrays;

/**
 * 插入排序
 *
 * O(n2)
 */
public class Insertion extends SortBase {


    public static void main(String[] args) {
//        int[] array = generate(100, 100);
        int[] array = {99, 45, 75, 84, 24, 72, 69, 51, 90, 93, 97, 19, 99, 36, 10, 12, 54, 37, 44, 14, 60, 29, 77, 60, 81, 65, 65, 49, 53, 71, 40, 20, 27, 90, 12, 43, 49, 17, 70, 80, 68, 21, 61, 19, 47, 28, 90, 38, 94, 81, 75, 6, 0, 64, 63, 64, 94, 38, 13, 62, 5, 67, 73, 36, 0, 22, 67, 82, 70, 8, 66, 43, 30, 11, 25, 60, 88, 69, 18, 80, 93, 76, 69, 5, 56, 10, 96, 4, 83, 67, 99, 9, 9, 63, 69, 10, 17, 6, 99, 89};
        int[] array1 = Arrays.copyOf(array, array.length);
        int[] array2 = Arrays.copyOf(array, array.length);
        int[] array3 = Arrays.copyOf(array, array.length);
        print(array);

//        print(shell2(array1));
//        print(shell(array, 1, 0));
        print(sort(array3));
        Arrays.sort(array2);

        print(array2);
        System.out.println(compare(array1, array2));
        System.out.println(compare(array3, array2));
    }


    //优化写法
    public static int[] sort(int array[]) {
        int swapN = 0;
        for (int i = 1, n = array.length; i < n; i++) {
            if (array[i] < array[i - 1]) {
                int tmp = array[i];
                int j = i;
                for (; j > 0; j--) {
                    if (tmp < array[j - 1]) {
                        swapN++;
                        array[j] = array[j - 1];
                    } else break;
                }
                array[j] = tmp;
            }
        }
        System.out.println("插入次数: " + swapN);
        return array;
    }

}
